package org.example.day;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/27 20:19
 */
public class Solution438 {

    public static void main(String[] args) {
        Solution438 s = new Solution438();
        List<Integer> list = s.findAnagrams("cbaebabacd", "abc");
        for (Integer value : list) {
            System.out.println(value);
        }
    }

    // 26字母题 可以使用数组存储 0~25  s.chatAt(0) - 'a'
    public List<Integer> findAnagrams(String s, String p) {

        if (s.length() < p.length()) {
            return new ArrayList<>();
        }

        //s的每个字母的数量 要大于 s.数量 否则不存在 字母异位词
        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> pMap = new HashMap<>();

        for (char c : s.toCharArray()) {
            sMap.putIfAbsent(c, 0);
            sMap.put(c, sMap.get(c) + 1);
        }

        for (char c : p.toCharArray()) {
            pMap.putIfAbsent(c, 0);
            pMap.put(c, pMap.get(c) + 1);
        }

        for (Character key : pMap.keySet()) {
            if(!sMap.containsKey(key)
                || pMap.get(key) > sMap.get(key)){
                //s不存在该字母 或者 字母数量少于p
                return new ArrayList<>();
            }
        }

        sMap.clear();
        for (int i = 0; i < p.length(); i++) {
            char c = s.charAt(i);
            sMap.putIfAbsent(c, 0);
            sMap.put(c, sMap.get(c) + 1);
        }

        List<Integer> res = new ArrayList<>();
        int end = p.length();
        for (int i = 0; i <= s.length() - p.length(); i++) {
            if(checkMapCount(sMap, pMap)){
                res.add(i);
            }
            if(i<s.length()-p.length()){
                sMap.put(s.charAt(i), sMap.get(s.charAt(i)) - 1);
                int last = end + i;
                sMap.putIfAbsent(s.charAt(last), 0 );
                sMap.put(s.charAt(last), sMap.get(s.charAt(last)) + 1);
            }
        }

        return res;
    }

    private boolean checkMapCount(HashMap<Character, Integer> sMap, HashMap<Character, Integer> pMap) {
        for (Character key : pMap.keySet()) {
            if(!sMap.containsKey(key)
                    || pMap.get(key) > sMap.get(key)){
                //s不存在该字母 或者 字母数量少于p
                return false;
            }
        }
        return true;
    }

    /**
     * @Description:
     * 1.不同字符和 可能相等， 比如 af / be
     * 2.时间复杂度过高
     * @auther: wyatt
     * @date: 20:28 2024/6/27
    */
    @Deprecated
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < p.length(); i++) {
            sum += p.charAt(i);
        }

        for (int i = 0; i <= s.length() - p.length(); i++) {
            int sub = 0;
            for (int j = 0; j < p.length(); j++) {
                sub+=s.charAt(i+j);
                if(sub > sum){
                    break;
                }
            }
            if(sum == sub){
                res.add(i);
            }
        }

        return res;
    }

}
